﻿#include "fill.h"
#include <sstream>

/************************* EdgeNode *************************/

EdgeNode::EdgeNode(POINT start, POINT end)
{
	// 找出两头以及斜率
	if (start.y > end.y) {
		ymax = start.y;
		ymin = end.y;
		x = end.x;
	}
	else if (start.y < end.y) {
		ymax = end.y;
		ymin = start.y;
		x = start.x;
	}
#ifdef FILLDEBUG
	if (start.y == end.y) { assert(0); }  // 不得出现 ymin = ymax，因为是扫描线
#endif
	dx = 1.0 * (start.x - end.x) / (start.y - end.y);
}

std::string EdgeNode::repr()
{
	std::stringstream ss;
	ss << "[" << "x=" << x << ", ymax="
		<< ymax << ", 1/k=" << dx << "]";
	return ss.str();
}

/************************* EdgeTable *************************/

EdgeTable::EdgeTable(EdgeNode& edge)
{
	this->edge_table.push_back(edge);
}

void EdgeTable::push(EdgeNode& edge)
{
	this->edge_table.push_back(edge);
	//std::list<EdgeNode>::iterator iter = this->edge_table.begin();
	//for (; iter != this->edge_table.end(); iter++) {
	//	if (edge.getX() > )
	//}
}

void EdgeTable::insertNewEdgeTable(EdgeTable& et)
{
	this->edge_table.insert(this->edge_table.end(), et.getBegin(), et.getEnd());
}

void EdgeTable::deleteOldEdgeNode(int y)
{
	for (std::list <EdgeNode>::iterator iter = edge_table.begin(); iter != edge_table.end();) {
		if (iter->getYmax() <= y) {  // 这里是小于等于，是一个细节
			// 这里erase之后it会变化，此时for循环中如果iter++会导致找不到iter
			// 产生cannot increment value-initialized list iterator 的错误
			this->edge_table.erase(iter++);
		}
		else {
			iter++;
		}
	}
}

void EdgeTable::sort()
{
	this->edge_table.sort();  // TODO: 这里为啥可以直接sort
}

std::vector<float> EdgeTable::calcIntersection()
{
	// 只有活性边表aet会调用该函数, 增量式更新当前扫描线对应活性边表中边的交点
	std::vector<float> ret;
	for (std::list <EdgeNode>::iterator iter = edge_table.begin(); iter != edge_table.end(); iter++) {
		iter->updateX();
		ret.push_back(iter->getX());  // 将所有交点的横坐标记录下来并返回
	}
	return ret;
}

std::string EdgeTable::repr()
{
	std::stringstream ss;
	for (auto edge : this->edge_table) {
		ss << edge.repr() << " ";
	}
	return ss.str();
}


/************************* Fill *************************/

Fill::Fill()
{
	this->nr_point = 0;
}

Fill::Fill(std::vector<POINT> points, int num)
{
	//this->P = std::make_unique<POINT[]>(num);
	this->P = points;
	this->nr_point = num;
	for (int i = 0; i < num; i++) {
		this->P[i] = points[i];
	}
	// 创建桶表
	//		1. 找出扫描线的最小值和最大值.  
	ymin = ymax = P[0].y;
	for (int i = 1; i < this->nr_point; i++) {
		ymin = ymin > P[i].y ? P[i].y : ymin;
		ymax = ymax < P[i].y ? P[i].y : ymax;
	}
	// 创建边表
	//		1. 遍历每条边
	for (int i = 0; i < this->nr_point; i++) {
		int j = (i + 1) % this->nr_point;  // 计算边的另一个顶点下标
		if (P[i].y == P[j].y) {  // 若边正好是扫描线, 不考虑
			continue;
		}
		EdgeNode edge(P[i], P[j]);
		// 移动到该边ymin（最下面的端点）所在的桶节点
		this->addNewEdge(edge);
	}
}

void Fill::addNewEdge(EdgeNode& edge)
{
	int scanline_num = edge.ymin;  // 需要加入到的桶表的key值
	std::map<int, EdgeTable>::iterator iter = this->bucket_table.find(scanline_num);
	if (iter == this->bucket_table.end()) {
		// 没找到则新建
		EdgeTable new_et(edge);
		this->bucket_table.insert(std::pair<int, EdgeTable>(scanline_num, new_et));
		this->scanline_keys.push_back(scanline_num);
	}
	else {  // 找到则插入
		iter->second.push(edge);
	}
}

void Fill::fill(COLORREF color)
{
	EdgeTable aet(this->bucket_table[this->ymin]);  // 初始化活性边表为新边表的第一个值
	// 需要测试aet的值对不对
	//std::cout << aet.repr();
	for (int y = ymin + 1; y <= ymax; y++) {  // 开始遍历每一条扫描线
		for (std::vector<int>::iterator iter = scanline_keys.begin(); iter != scanline_keys.end(); iter++) {
			if (*iter == y) {  // 存在新边
				aet.insertNewEdgeTable(this->bucket_table[*iter]); // 将新边(一维列表形式)全部加进aet，aet依然是一维列表
				this->scanline_keys.erase(iter);  // 从key列表中删除该元素
				break;
			}
		}

		// 删除边ymax小于当前扫描线的边
		aet.deleteOldEdgeNode(y);

		// 对活性边表排序
		aet.sort();

		// 求交点
		std::vector<float> jd = aet.calcIntersection();

		// 得到所有交点即可通过边标志算法填充颜色(因为不一定是凸多边形)
		// 这里也可以使用栅栏填充, 配对填充等, 得到交点了就可以为所欲为
		bool is_inside = false;
		int jd_num = jd.size();
		for (int i = 0; i < jd_num; i++) {
			if (is_inside == false) {
				is_inside = true;
			}
			else {
				for (int x = jd[i - 1]; x < jd[i]; x++) {
					putpixel(x, y, color);
				}
				is_inside = false;
			}
		}
		// end for
	}
}

/* For Test */
std::string Fill::repr()
{
	std::stringstream ss;
	//ss << "桶表信息：" << std::endl;
	for (auto bucket : this->bucket_table) {
		ss << bucket.first << " --> " << bucket.second.repr() << std::endl;
	}
	return ss.str();
}

void Fill::show()
{
	std::cout << "多边形点信息: ";
	for (int i = 0; i < this->nr_point; i++) {
		std::cout << i + 1 << ":(" << this->P[i].x << ", " << this->P[i].y << ") ; ";
	}

	std::cout << std::endl << "新边表: " << std::endl;
	std::cout << this->repr();

	std::cout << std::endl << "新边表扫描线y值: ";
	for (int sl : this->scanline_keys) {
		std::cout << sl << " ; ";
	}
}
